package com.rising.face.ali.bishi.fastsort;

import java.util.Arrays;

/**
 * @Author: rising
 * @Description:
 * 快排的思想，就是找到一个key，然后第一遍从尾部找到一个key小的，然后置换，然后从头到置换后的位置找一个比key大的进行置换
 * 当左指针等于右指针时，此时关键之key左边的一定比key小，右边的一定比key大，但是左右两边无序，此时需要递归左右两边
 * @Date: create in 2021/2/19 14:57
 */
public class FastSort {

    public static void main(String[] args) {
        int[] array = {10,70,2,5,30,90,20,100,34,56};
        System.out.println("排序前：" + Arrays.toString(array));
        FastSort.sort(array, 0, array.length - 1);
        System.out.println("排序后：" + Arrays.toString(array));
    }

    public static void sort(int[] a,int low,int high) {
        int start = low;
        int end = high;
        int key = a[low];
        while (end>start) {
            //从后往前比较
            while(end>start && a[end]>=key)
            //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //从前往后比较
            while(end>start && a[start]<=key)
            //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        }
        //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的
        //值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        //递归
        if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
        if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1 到最后一个
    }
}
